package com.wfm.leetcode.editor.cn;

import com.wfm.common.DisjointSets;
import java.util.ArrayList;
import java.util.List;

/**
 * 本题解法一采用深度优先遍历，找到ans个连通分量
 * 需要连起来的最少边就是ans-1个。
 * O(n+m) m是数组connections的长度，n节点个数
 * O(n+m) m为存储所有边需要的空间，n为深度优先搜索中使用的栈空间
 *
 * 解法二并查集
 */
public class POne319连通网络的操作次数{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    boolean[] visited;
    List<Integer>[] edges;
    public int makeConnected(int n, int[][] connections) {

        // 边的个数只能比节点数小1，小多了就连不起来
        if(connections.length<n-1){
            return -1;
        }

        // 把边的关系转换成以数组下标为节点，值为连接的边。
        // 比如 【0,1】[0,2] ==> [[1,2],[0],[0]]
        //                         0    1   2
        edges = new List[n];
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < connections.length; i++) {
            edges[connections[i][0]].add(connections[i][1]);
            edges[connections[i][1]].add(connections[i][0]);
        }

        visited = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if(!visited[i]){
                dfs(i);
                ans++;
            }
        }
        return ans-1;

    }
    public void dfs(int i){
        visited[i]=true;
        for (int j = 0; j < edges[i].size(); j++) {
            if(!visited[edges[i].get(j)]){
                dfs(edges[i].get(j));
            }
        }
    }

    // 方法二：并查集=========
//    public int makeConnected1(int n, int[][] connections) {
//        if(connections.length<n-1) return -1;
//
//        DisjointSets disjointSets = new DisjointSets(n);
//        for(int[] con:connections){
//            disjointSets.merge(con[0],con[1]);
//        }
//
//        return disjointSets.setCount-1;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne319连通网络的操作次数().new Solution();
    }
}